//142. 环形链表 II
//思路：先判断是否为环形链表，是环形链表再求环的入口点
//1.快慢指针判断环形链表，如果fast = slow就说明是环形链表 
//2.在环形链表的基础上，将相遇点记下来
//3.写一个内层循环，meet != head为循环判断，接下来meet与head都分别一步步的走
//4.跳出内层循环就是meet = head，这时就说明找到了入环点。返回head/meet都是可以的。

#include <stdio.h>
struct ListNode {
	int val;
	struct ListNode* next;
};
struct ListNode* detectCycle(struct ListNode* head) {
	struct ListNode* slow = head, * fast = head;

	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;

		if (slow == fast)//判断是环形链表，并且找到相遇点
		{
			struct ListNode* meet = slow;//记下相遇点
			while (head != meet)//找入环点
			{
				head = head->next;
				meet = meet->next;
			}
			return head;//返回入环点(head/meet都可以)
		}
	}
	return NULL;//不成环形链表
}